package Text5;
import java.util.*;
public class Main {
    public static int N = 510,n,m, max = 0x3f3f3f3f;
    public static int[][] g = new int[N][N];//存每个点之间的距离
    public static int[] dist = new int[N];//存每个点到起点之间的距离
    public static boolean[] st = new boolean[N];//存已经确定了最短距离的点

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n=scanner.nextInt();
        m=scanner.nextInt();
        for(int i = 1 ; i <= n ; i ++ ){
            Arrays.fill(g[i],max);
        }
        Arrays.fill(dist,max);
        dist[1]=0;
        while (m-->0){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            g[a][b]=Math.min(g[a][b],c);
        }
        System.out.println(dijkstra());
    }

    private static int dijkstra() {
        for (int i = 0; i < n; i++) {
            int min=-1;
            for (int j = 1; j <=n ; j++) {
                if(!st[j]&&(min==-1||dist[min]>dist[j])){
                    min=j;
                }
            }
            st[min]=true;
            for (int j = 1; j <=n ; j++) {
                if(dist[j]>dist[min]+g[min][j]){
                    dist[j]=dist[min]+g[min][j];
                }
            }
        }
        if(dist[n]==max){
            return -1;
        }else {
            return dist[n];
        }
    }
}
